Lambda the Ultimate

Generics of a Higher Kind. Adriaan Moors, Frank Piessens, and Martin Odersky.

With Java 5 and C# 2.0, first-order parametric polymorphism was introduced in mainstream object-oriented programming languages under the name of generics. Although the first-order variant of generics is very useful, it also imposes some restrictions: it is possible to abstract over a type, but the resulting type constructor cannot be abstracted over. This can lead to code duplication. We removed this restriction in Scala, by allowing type constructors as type parameters and abstract types. This paper presents the design and implementation of the resulting type constructor polymorphism. It combines type constructor polymorphism with implicit parameters to yield constructs similar to, and at times more expressive than, Haskell’s constructor type classes. The paper also studies interactions with other object-oriented language constructs, and discusses the gains in expressiveness.

Many readers will already be aware that Scala has added support for higher-kinded generics, related to Haskell's type constructor classes. I believe Scala is the first language to provide this capability in an OO "generics" framework. This ECOOP submission presents this work, with many practical examples.

(Consider this penance for my last post...)

A Dialogue on Infinity, between a mathematician and a philosopher. Alexandre Borovik and David Corfield.

A new blog... From the first post:

The project concentrates on one of the principal purposes of the Exploring the Infinite Program:

To understand the nature of and the role played by conceptualizations of infinity in mathematics.

It will be shaped as a dialogue between a mathematician (AB) and a philosopher (DC) and will address one of the central paradoxes of mathematics:

why are most uses of infinity in mathematics restricted to the recycling of a small number of “canonical” and ubiquitous structures?

...To put the study of infinity on a firm basis, we first have to discuss the issue of the identity and “sameness” of mathematical objects: infinity of what?

This is pretty far out for LtU, but I suspect it will interest some more philosophically inclined readers. They will look at a number of disciplines, including computer science.

(I feel like maybe even "Theory" is not theoretical for this. Therefore I am also calling it "Fun".)

Yukiyoshi Kameyama, Oleg Kiselyov, Chung-chieh Shan. Closing the Stage: From Staged Code to Typed Closures. PEPM'08. (code)

Code generation lets us write well-abstracted programs without performance penalty. Writing a correct code generator is easier than building a full-scale compiler but still hard. Typed multistage languages such as MetaOCaml help in two ways: they provide simple annotations to express code generation, and they assure that the generated code is well-typed and well-scoped. Unfortunately, the assurance only holds without side effects such as state and control. Without effects, generators often have to be written in a continuation-passing or monadic style that has proved inconvenient. It is thus a pressing open problem to combine effects with staging in a sound type system.

This paper takes a first step towards solving the problem, by translating the staging away. Our source language models MetaOCaml restricted to one future stage. It is a call-by-value language, with a sound type system and a small-step operational semantics, that supports building open code, running closed code, cross-stage persistence, and non-termination effects. We translate each typing derivation from this source language to the unstaged System F with constants. Our translation represents future-stage code using closures, yet preserves the typing, alpha-equivalence (hygiene), and (we conjecture) termination and evaluation order of the staged program...

Essentially, representation of staged programs in an unstaged language turns out to be related to typechecking/typed compilation: typechecking is a stage. While this basic idea is straightforward, the work presented in the paper is rather intricate and depends on previous work on typed compilation. Oleg will be able to put this work in context in the forum, hopefully.

A short audio presentation (Avi speaks for less than ten minutes, I guess), about the lessons the Ruby community should learn from Smalltalk. It's mainly about turtles-all-the-way-down, but Self (fast VMs), GemStone (transactional distributed persistence), Seaside (web frameworks) are also mentioned briefly.

A write-up of the Commercial Users of Functional Programming meeting held this October is available, for those of us who didn't attend. The write-up is well written and thought provoking (it was written by Jeremy Gibbons, so that's not a surprise).

The goal of the Commercial Users of Functional Programming series of workshops is to build a community for users of functional programming languages and technology. This, the fourth workshop in the series, drew 104 registered participants (and apparently more than a handful of casual observers).

It is often observed that functional programming is most widely used for language related projects (DSLs, static analysis tools and the like). Part of the reason is surely cultural. People working on projects of this type are more familiar with functional programming than people working in other domains. But it seems that it may be worthwhile to discuss the other reasons that make functional languages suitable for this type of work. There are plenty of reasons, many of them previously discussed here (e.g., Scheme's uniform syntax, hygiene, DSELs), but perhaps the issue is worth revisiting, seeing as this remains the killer application for functional programming, even taking into account the other types of project described in the workshop.

And Shin-Cheng Mu gives a rather accessible algebraic proof.

There's lots to say about this observation, but apart from saying I was surprised by it, I will leave comment to the comments.

Computation Orchestration: A Basis for Wide-Area Computing, Jayadev Misra and William Cook. JSSM 2006.

The widespread deployment of networked applications and adoption of the internet has fostered an environment in which many distributed services are available. There is great demand to automate business processe and workflows among organizations and individuals. Solutions to such problems require orchestration of concurrent and distributed services in the face of arbitrary delays and failures of components and communication.

We propose a novel approach, called Orc for orchestration, that supports a structured model of concurrent and distributed programming. This model assumes that basic services, like sequential computation and data manipulation, are implemented by primitive sites. Orc provides constructs to orchestrate the concurrent invocation of sites to achieve a goal -- while managing time-outs, priorities, and failure of sites or communication.

The idea of orchestration languages is one of the good ideas to come out of the web services world. Orc is an elegant little process-calculus-inspired programming language that illustrates and embodies the key ideas, and I'd recommend studying it to anyone who has even a passing inclination to design languages or libraries for "mashup" style programming.

If this sounds like a worthy goal, or if you are simply interested in the use of proof assistants for rogramming language research, you don't want to miss upcoming tutorial.

Nearly two years ago I posted Beyond LINQ: A Manifesto For Distributed Data-Intensive Programming on this forum. Now, within a period of a few weeks, both LINQ as well as a rather different realization of my original post-LINQ plans are shipping. I am particularly proud to announce that a community preview of Volta is available for immediate download from http://labs.live.com/volta/.

Volta is a collection of tools that enable programmers to develop asynchronous and distributed (including but not limited to AJAX) applications by successive refactoring of normal, sequential, programs written in standard .NET languages (this CTP requires Visual Studio 2008) and deploy the resulting applications on a wide variety of target platforms (this CTP supports Internet Explorer and FireFox). Or as I sometimes say when I am trying to sound like a marketing person “ Volta stretches the .NET platform to cover the Cloud.” Volta allows programmers to concentrate on the essential complexity involved in building AJAX application and have our tools take care of the gory details and accidental complexity.

When using Volta, programmers can specify their intent of running certain classes on the server by decorating the class declaration using a [RunAtOrigin()] attribute. The Volta post-compiler then weaves in (you never heard me say that I thought AOP was a bad idea did you :-) all the necessary boilerplate code to partition the original program to run across multiple tiers. Similarly, programmers can create an asynchronous version of a method by decorating an empty method declaration of a related signature with an [Async()] attribute. Again, the Volta post-compiler takes care of all the boilerplate code under the hood to enable asynchronous invocation of the target method. Another pain point in writing AJAX applications is supporting multiple browsers. To ease this pain, Volta includes Scott Isaac’s cross-browser compatibility layer that is also used in Windows Live.

Volta embraces the Lean Programming principle of delaying irreversible decisions until the last possible responsible moment. In particular we want to delay decisions about distribution as long as possible. To help developers make informed decisions about the distribution a program across tiers, the Rotunda profiler from MSR is fully integrated in the Volta toolchain. By automatically injection hooks for all interesting events, Rotunda creates trace information that can be inspected using the standard Service Trace Viewer tool.

When I speak about Volta or show a demo, the best compliment I can get is when people say this is “trivial” or “really straightforward”. The best tools are those that do their work unobtrusive hidden in the background. Anyway, with the holidays around the corner you may have some spare cycles to give Volta a spin and let us know what you think!

A short interview with Brian Grant (of PeakStream and currently Google). From SD Times, Nov. 15, 2007.

SD Times: Is concurrency too difficult for developers accustomed to linear programming to grasp?

Brian Grant: It is challenging, but I don’t think it’s too challenging. I do think certain languages, especially C and C++, make it very challenging to write robust big multithreaded systems. Basically, they have features that are hostile to concurrency.

Does your experience in compilers give you a different perspective than the average developer?

[...]
Higher-level languages favor ease of correctness over ease of performance. For example, in functional languages such as Haskell, the code you write does not have any side effects. The model is that they don’t modify existing data; they generate new data. The advantage is that it’s easier for the compiler to reason about what different components of the code can do.
[...]